import java.util.*;

public class TestDemo {
    public int maxSubArray(int[] num){
        if(num==null||num.length==0){
            return 0;
        }
        int cur=num[0];
        int max=cur;
        for(int i=1;i<num.length;i++){
            cur=Math.max(cur,0)+num[i];
            max=Math.max(cur,max);
        }return max;
    }
    //你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
    //返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
   //第一种（最大序数和的做法）
    public int maxProfit2(int []prices){
        if(prices==null||prices.length==0){
            return 0;
        }
        int length=prices.length;
        int cur=0;
        int max=cur;
        for(int i=1;i<length;i++){
            cur=Math.max(cur,0)+prices[i]-prices[i+1];
            max=Math.max(max,cur);
        }return max;
    }
    //第二种
    public static int maxProfit1(int []prices){
        if(prices==null||prices.length==0){
            return 0;
        }int maxPro=0;
        int min=prices[0];
        for(int i=0;i<prices.length;i++){
            min=Math.min(prices[i],min);
            maxPro=Math.max(prices[i]-min,maxPro);
        }return maxPro;
    }
    //假设你正在爬楼梯。需要 n 阶你才能到达楼顶。(每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？)
    //第一种
    public static int Fibonacci(int n,int a,int b){
        if(n<=1){
            return b;
        }
        else{
            return Fibonacci(n-1,b,a+b);
        }
    }
    public static int climbStairs1(int n){
        return Fibonacci(n,1,1);
    }
    //假设你正在爬楼梯。需要 n 阶你才能到达楼顶。（每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？）
    //第二种
    public static int climbStairs(int n){
        if(n<=2){
            return n;
        }int first=1;
        int second=2;
        int sum=0;
        while(n-->2){
            sum=first+second;
            first=second;
            second=sum;
        }return sum;
    }

    public static void main(String[] args) {
        System.out.println(climbStairs(21));
    }
    public int maxProfit(int[] prices){
        if(prices==null||prices.length==0){
            return 0;
        }
        int index=0;
        int length=prices.length;
        int total=0;
        while(index<length){
            while(index<length-1&&prices[index]>prices[index+1]){
                index++;
            }int min=prices[index];
            while(index<length-1&&prices[index]<prices[index+1]){
                index++;
            }total+=prices[index++]-min;
        }return total;
    }
    //将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
//反向链表
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode newHead=new ListNode(-1);
        ListNode tem=newHead;
        while(list1!=null||list2!=null){
            if(list1.val<list2.val){
                tem.next=list1;
                tem=tem.next;
                list1=list1.next;
            }else{
                tem.next=list2;
                tem=tem.next;
                list2=list2.next;
            }
        }if(list1!=null){
            tem.next=list1;
        }if(list2!=null){
            tem.next=list2;
        }return newHead;
    }
    public ListNode reverseList(ListNode head) {
        ListNode prev=null;
        ListNode cur=head;
        if(head!=null){
            return null;
        }while(cur!=null){
            ListNode curNext=cur.next;
            cur.next=prev;
            prev=cur;
            cur=curNext;
        }return prev;
    }
    //给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点
    public ListNode removeNthFormend(ListNode head,int n){
        if(head==null){
            return null;
        } ListNode fast=head;
        ListNode slow=head;
        while(n>0){
           fast=fast.next;
           n--;
        }while(fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }slow.next=slow.next.next;
        return head;
    }
    public boolean isAnagram(String s,String t){
        int []count=new int [26];
        char[]ch=s.toCharArray();
        char[]ch2=s.toCharArray();
        if(s.length()!=t.length()){
            return false;
        }for(int i=0;i<s.length();i++){
           count[ch[i]-'a']++;
        }for(int i=0;i<s.length();i++){
            count[ch[i]-'s']--;
        }
        for(int c:count){
            if(c!=0){
                return false;
            }
        }return true;
    }
    //给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
    //第一种
    public int fristsUniqChar(String s){
        Map<Character,Integer>map=new HashMap<>();
        char[]array=s.toCharArray();
        for(char ch:array){
            map.put(ch,map.getOrDefault(ch,0)+1);
        }for(int i=0;i<s.length();i++){
            if(map.get(array[i])==1){
                return i;
            }
        }return -1;

    }//第二种
    public int fristUniqChar(String s){
        char[]ch=s.toCharArray();
        int []count=new int [26];
        for(int i=0;i<s.length();i++){
            count[ch[i]-'a']++;
        }for(int j=0;j<s.length();j++){
            if(count[ch[j]]==1){
                return j;
            }
        }return -1;
    }
    public static void main1(String[] args) {
        List<String>course=new ArrayList<>();
        //添加元素
        course.add("大卷");
        course.add("小卷");
        course.add("大蛋");
        course.add("二蛋");
        //按顺序打印
        System.out.println(course);
        //类似于数组下标访问
        System.out.println(course.get(1));
        course.set(0,"卷少");
        System.out.println(course);
        //截取部分[1,3)
        List<String>subCourses=course.subList(1,3);
        System.out.println(subCourses);
        //重新构造
        List<String>course2=new ArrayList<>(course);
        System.out.println(course2);

        List<String>course3=new LinkedList<>(course);
        System.out.println(course3);
        //引用的转换
        ArrayList<String>course4=(ArrayList<String>) course2;
        System.out.println(course4);
        //LinkedList<String> c =(LinkedList<String>course2;错误的类型
        LinkedList<String>course5=(LinkedList<String>) course3;
        System.out.println(course5);
        //ArrayList<String>c=(ArrayList<String>) course3;错误类型
    }
}
